#include <iostream>
#include <vector>
#include <stack>


struct ListNode
{
    int val;
    ListNode*next;
};

void add_node(ListNode*&head,int data)
{
    ListNode*node = new ListNode;
    node->val = data;
    node->next = nullptr;

    if (!head)
        head = node;
    else 
    {
        ListNode*temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = node;
    }
}

void print_list(ListNode*head)
{
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<"\n";
        temp = temp->next;
    }
}

// 思路1 分奇偶两种思路处理
// bool is_pail(ListNode*head)
// {
//     // 首先判空，不然整个都崩
//     if (!head||!head->next)
//     {
//         return true;
//     }

//     // 获取链表长度
//     int n = 0;
//     ListNode*temp = head;
//     while (temp)
//     {
//         n++;
//         temp = temp->next;  // 再忘我打死你
//     }

//     // 奇偶进行分流
//     if (n&1)
//     {

//     }
//     else 
//     {
//         std::stack<int>s;
//         // 偶数规则:将所有元素push进栈，遇见相同元素就相消？？？
//         // 不行，这个思路完全就是大勾栏
        
//     }
// }

// 思路2 倒序前后两次序列化判断是否相等
bool isPail(ListNode*&head)
{
    // 首先判空 
    if (!head||!head->next)
    {
        return true;
    }

    // 第一次序列化
    std::vector<int>first;
    ListNode*temp = head;
    while (temp)
    {
        first.push_back(temp->val);
        temp = temp->next;
    }

    // 将链表反转后
    ListNode*prev = nullptr;    
    temp = head;
    while (temp)
    {
        ListNode*post = temp->next;
        temp->next = prev;
        prev = temp;
        temp = post;
    }
    head = prev;

    // 第二次序列化
    std::vector<int>second;
    temp = head;
    while (temp)
    {
        second.push_back(temp->val);
        temp = temp->next;
    }

    // 将两次进行比较发现不相等就返回false
    int n = second.size();
    for (int i = 0;i < n;i++)
    {
        if (first[i] != second[i])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    ListNode*head = nullptr;
    add_node(head,1);
    add_node(head,2);
    add_node(head,3);
    add_node(head,2);
    add_node(head,2);

    std::cout<<isPail(head)<<"\n";
    return 0;
}
// 整个函数漏洞百出啊
// 首先反转链表需要把尾节点重新赋值给头节点
// 我甚至能解释刚才为什么两次都是true
// 第一次因为就是回文序列，
// 第二次因为，反转后头节点变为尾节点，而获取序列长度时使用尾节点相当于只有一个元素，
// 并且往链表中放入元素时采用的是push_back()
// 因此如果使用顺次比较的话，第一个相等，然后循环n==1自然结束。。。。。。。。。
// 所以下次链表反转一定要一定要一定要单独封装一个函数
// 